#ifndef COMMON_H
#define COMMON_H

#include <vector>
#include <cassert>

struct ListNode
{
	int y, z;
	ListNode(int _y = 0, int _z = 0)  : y(_y), z(_z) {}
};

struct ListNode2
{
	int x, y, z;
	ListNode2(int _x = 0, int _y = 0, int _z = 0)  : x(_x), y(_y), z(_z) {}
};


template<class T>
struct ListItem {
    T data;
    ListItem<T> *pre, *nxt;
	ListItem() : pre(NULL), nxt(NULL) { }
    ListItem(T d, ListItem* p, ListItem* n) : data(d), pre(p), nxt(n) { }
};

template<class T>
class List;

template<class T>
class LIterator {
public:
	friend class List<T>;
    LIterator(ListItem<T>* header = NULL) : _header(header) { }
    T& operator*() const { return _header -> data;}
    T* operator->() const { return &(operator*());}
    LIterator& operator++() {
        _header = _header -> nxt;
        return *this;
    }
    LIterator operator++(int) {
		LIterator tmp = *this;
        _header = _header -> nxt;
        return tmp;
    }
    LIterator& operator--() {
        _header = _header -> pre;
        return *this;
    }
    LIterator operator--(int) {
		LIterator tmp = *this;
        _header = _header -> pre;
        return tmp;
    }
    bool operator!= (const LIterator& other) {
        return (_header != other._header);
    }

private:
    ListItem<T>* _header;
};


template<class T>
class List
{
public:
    List(int _n = 0) : tail(NULL), _mem(_n), cnt(0) {}

    void push_back(const T &t) {
		if (tail == NULL) {
			tail = new_item(t, NULL, NULL);
			return;
		}
		tail->nxt = new_item(t, tail, NULL);
		tail = tail->nxt;
    }

	// Insert t right before iter.
	void insert(LIterator<T> iter, const T &t)
	{
		assert(iter._header != NULL);
		ListItem<T> *new_it = new_item(t, iter._header->pre, iter._header);
		if (iter._header->pre != NULL) iter._header->pre->nxt = new_it;
		iter._header->pre = new_it;
	}

	void erase(LIterator<T> iter)
	{
		if (iter._header->nxt) iter._header->nxt->pre = iter._header->pre;
		else tail = tail->pre;
		if (iter._header->pre) iter._header->pre->nxt = iter._header->nxt;
	}

	ListItem<T>* new_item(const T &t, ListItem<T>* pre, ListItem<T>* nxt)
	{
		assert(cnt < _mem.size() && cnt >= 0);
		_mem[cnt++] = ListItem<T>(t, pre, nxt);
		return &(_mem.front()) + cnt - 1;
	}

	// The list will be cleared at the same time!
	void resize(int _n)
	{
		clear();
		_mem.resize(_n);
	}

	void clear()
	{
		tail = NULL;
		cnt = 0;
	}

	int used_size()
	{
		return cnt;
	}

	int size()
	{
		int tmp = 0;
		for (LIterator<T> iter = begin(); iter != end(); --iter)
			++tmp;
		return tmp;
	}

    LIterator<T> begin() { return LIterator<T>(tail); }
    LIterator<T> end() { return LIterator<T>(NULL); }

private:
    ListItem<T>* tail;
	std::vector<ListItem<T> > _mem;
	int cnt;
};

template<class T>
class Stack
{
public:
    Stack(int _n = 0) : s_(_n), top_(0) {}
    T& top()
	{
		assert(top_ > 0);
		return s_[top_ - 1];
	}
	bool empty()
	{
		return top_ == 0;
	}
	void push(const T &o)
	{
		assert(top_ < s_.size());
		s_[top_++] = o;
	}
	void clear()
	{
		top_ = 0;
	}
	void pop()
	{
		--top_;
	}
	void resize(int _n)
	{
		s_.resize(_n);
	}
private:
	int top_;
	std::vector<T> s_;
};




#endif /* COMMON_H */
